package _14_滑动窗口;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class _438_找到字符串中所有字母异位词 {

    public static void main(String[] args) {
        _438_找到字符串中所有字母异位词 v = new _438_找到字符串中所有字母异位词();

        List<Integer> anagrams = v.findAnagrams("abab", "ab");

        System.out.println(anagrams);
    }

    // 对于滑动窗口问题，可以首先固定窗口大小，然后一个进，一个出
    // 固定滑动窗口大小，构造俩个数组，比较内容相同，则是答案
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> results = new ArrayList<>();
        char[] chars1 = s.toCharArray();
        char[] chars2 = p.toCharArray();
        int[] ch1 = new int[26];
        int[] ch2 = new int[26];
        int len1 = s.length();
        int len2 = p.length();
        if (len2 > len1) return results;
        for (int i = 0; i < len2; i++) {
            // 构造比较数组
            ch2[chars2[i] - 'a']++;
            // 构造初始滑动窗口
            ch1[chars1[i] - 'a']++;
        }
        if (Arrays.equals(ch1, ch2)) {
            results.add(0);
        }
        // 滑动窗口移动，一个进，一个出
        for (int i = len2; i < len1; i++) {
            // 进
            ch1[chars1[i] - 'a']++;
            // 出
            ch1[chars1[i - len2] - 'a']--;
            if (Arrays.equals(ch1, ch2)) {
                results.add(i - len2 + 1);
            }
        }
        return results;
    }

    // 0(n)时间复杂度，方法比较巧妙
    public List<Integer> findAnagrams2(String s, String p) {
        List<Integer> list = new ArrayList<>();
        char[] chars1 = s.toCharArray();
        char[] chars2 = p.toCharArray();
        int[] charCount = new int[26];
        int len1 = chars1.length;
        int len2 = chars2.length;
        for (char c : chars2) {
            charCount[c - 'a']++;
        }
        int left = 0, right = 0;
        // 滑动窗口左范围
        while (left <= len1 - len2) {
            // 右指针移动
            while (right < left + len2 && charCount[chars1[right] - 'a'] >= 1) {
                charCount[chars1[right] - 'a']--;
                right++;
            }
            if (right - left == len2) {
                list.add(left);
            }
            // 恢复默认数据
            charCount[chars1[left] - 'a']++;
            left++;
        }
        return list;
    }

    public List<Integer> findAnagrams1(String s, String p) {
        List<Integer> results = new ArrayList<>();
        int[] ins = new int[26];
        int pLen = p.length();
        for (int begin = 0; begin < pLen; begin++) {
            ins[p.charAt(begin) - 'a']++;
        }
        int end = s.length() - p.length() + 1;
        // 滑动窗口，找到字母异位词
        for (int begin = 0; begin < end; begin++) {
            boolean hasFalse = false;
            int[] temp = new int[26];
            System.arraycopy(ins, 0, temp, 0, 26);
            for (int j = begin; j < begin + pLen; j++) {
                if (--temp[s.charAt(j) - 'a'] < 0) {
                    hasFalse = true;
                    break;
                }
            }
            if (hasFalse) continue;
            // 判断所有元素是否为0
            for (int i1 : temp) {
                if (i1 != 0) {
                    hasFalse = true;
                    break;
                }
            }
            if (!hasFalse) results.add(begin);
        }
        return results;
    }
}
